/**
 * This file is part of Sonedyan.
 * 
 * Sonedyan is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public
 * License as published by the Free Software Foundation;
 * either version 3 of the License, or (at your option) any
 * later version.
 *
 * Sonedyan is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied
 * warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
 * PURPOSE.  See the GNU General Public License for more
 * details.
 *
 * You should have received a copy of the GNU General Public
 * License along with Octave; see the file COPYING.  If not
 * see <http://www.gnu.org/licenses/>.
 * 
 * Copyright (C) 2009-2012 Jimmy Dubuisson <jimmy.dubuisson@gmail.com>
 */

package org.unige.mpej.eckmann.sonedyan.utils;

import java.awt.geom.Point2D;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.PrintWriter;
import java.util.Collection;
import java.util.Hashtable;
import java.util.LinkedList;
import java.util.Random;
import java.util.Set;

import org.apache.commons.collections15.Transformer;
import org.apache.commons.collections15.functors.StringValueTransformer;
import org.apache.log4j.Logger;
import org.unige.mpej.eckmann.sonedyan.bean.Edge;
import org.unige.mpej.eckmann.sonedyan.bean.Vertex;
import org.unige.mpej.eckmann.sonedyan.graph.transformer.EdgeTransformer;
import org.unige.mpej.eckmann.sonedyan.graph.transformer.GraphTransformer;
import org.unige.mpej.eckmann.sonedyan.graph.transformer.HyperEdgeTransformer;
import org.unige.mpej.eckmann.sonedyan.graph.transformer.VertexTransformer;

import edu.uci.ics.jung.graph.DirectedSparseGraph;
import edu.uci.ics.jung.graph.Graph;
import edu.uci.ics.jung.graph.SparseGraph;
import edu.uci.ics.jung.graph.SparseMultigraph;
import edu.uci.ics.jung.graph.UndirectedGraph;
import edu.uci.ics.jung.graph.UndirectedSparseGraph;
import edu.uci.ics.jung.graph.util.EdgeType;
import edu.uci.ics.jung.graph.util.Pair;
import edu.uci.ics.jung.io.GraphMLWriter;
import edu.uci.ics.jung.io.PajekNetWriter;
import edu.uci.ics.jung.io.graphml.EdgeMetadata;
import edu.uci.ics.jung.io.graphml.GraphMLReader2;
import edu.uci.ics.jung.io.graphml.GraphMetadata;
import edu.uci.ics.jung.io.graphml.HyperEdgeMetadata;
import edu.uci.ics.jung.io.graphml.NodeMetadata;

/**
 * Set of graph util methods
 */
public class GraphUtils
{
	private static Logger log = Logger.getLogger(org.unige.mpej.eckmann.sonedyan.utils.GraphUtils.class);
	
	public static final String PAJEK_FILENAME = "pajek.net";
	public static final String GRAPHML_FILENAME = "graphml.xml";
	public static final String GML_FILENAME = "graph.gml";
	
	/**
	 * get sorted vector of graph clusters by size
	 */
	public static <V extends Vertex, E extends Edge> LinkedList<Set<V>> getSortedGraphClusters(Set<Set<V>> clusters)
	{
		try
		{
			LinkedList<Set<V>> sortedClusters = new LinkedList<Set<V>>();
			
			for (Set<V> cluster : clusters)
			{
				if (sortedClusters.size() == 0)
				{
					sortedClusters.add(cluster);
				}
				else if (sortedClusters.size() == 1)
				{
					int size = cluster.size();
					
					if (size <= sortedClusters.get(0).size())
					{
						sortedClusters.add(0, cluster);
					}
					else
					{
						sortedClusters.add(1, cluster);
					}
				}
				else
				{
					int size = cluster.size();
					int sortedSize = sortedClusters.size();
					
					for (int i = 0; i < sortedSize - 1; i++)
					{
						if (size <= sortedClusters.get(i).size())
						{
							sortedClusters.add(i, cluster);
							break;
						}
						else if (size >= sortedClusters.get(i).size() && size <= sortedClusters.get(i + 1).size())
						{
							sortedClusters.add(i + 1, cluster);
							break;
						}
						else if (i == (sortedSize - 2))
						{
							if (size > sortedClusters.get(i + 1).size())
							{
								sortedClusters.add(sortedSize, cluster);
							}
							else
							{
								sortedClusters.add(sortedSize - 1, cluster);
							}
						}
					}
				}
				
			}
			
			return sortedClusters;
		}
		catch(Exception e)
		{
			log.error("Unable to get sorted vector of graph clusters: " + e.getMessage());
			return null;
		}
	}
	
	/**
	 * get multigraph snapshot
	 * 
	 * NB: edges of the multigraph are kept if their time validity lies within the specified boundaries
	 */
	public static <V extends Vertex, E extends Edge> Graph<V, E> getMultiGraphSnapshot(SparseMultigraph<V, E> g, long time, long timeLag)
	{
		try
		{
			Graph<V, E> graph = new SparseGraph<V, E>();
			
			Hashtable<String, V> idActors = new Hashtable<String, V>();
		
			Collection<V> actors = g.getVertices();

			for (V v : actors)
			{
				graph.addVertex(v);
				idActors.put(v.getId(), v);
			}
			
			Collection<E> links = g.getEdges();
			
			// undirected graph
			if (g.getDefaultEdgeType() == EdgeType.UNDIRECTED)
			{
				for (E e : links)
				{
					Pair<V> pair = g.getEndpoints(e);
					V fromActor = idActors.get(pair.getFirst().getId());
					V toActor = idActors.get(pair.getSecond().getId());
					
					if (!graph.isNeighbor(fromActor, toActor) && fromActor != toActor)
					{
						long startTime = e.getStartDate().getTime();
						long endTime;
						
						// set the end date in case the link is ponctual
						if (e.getEndDate() != null) { endTime = e.getEndDate().getTime(); }
						else { endTime = startTime; }
						
						if ((startTime >= (time - timeLag) && startTime <= (time + timeLag)) 
								|| (endTime >= (time - timeLag) && endTime <= (time + timeLag) ) )
						{
							graph.addEdge(e, fromActor, toActor, EdgeType.UNDIRECTED);
						}
					}
				}
			}
			// directed graph
			else
			{
				for (E e : links)
				{
					V fromActor = idActors.get(g.getSource(e).getId());
					V toActor = idActors.get(g.getDest(e).getId());
					
					if (!(graph.isSource(fromActor, e) && graph.isDest(toActor, e)) && fromActor != toActor)
					{
						long startTime = e.getStartDate().getTime();
						long endTime;
						
						// set the end date in case the link is ponctual
						if (e.getEndDate() != null) { endTime = e.getEndDate().getTime(); }
						else { endTime = startTime; }
						
						if ((startTime >= (time - timeLag) && startTime <= (time + timeLag)) 
								|| (endTime >= (time - timeLag) && endTime <= (time + timeLag) ) )
						{
							graph.addEdge(e, fromActor, toActor, EdgeType.DIRECTED);
						}
					}
				}
			}
			
			return graph;
		}
		catch(Exception e)
		{
			log.error("Unable to get multigraph snapshot: " + e.getMessage());
			return null;
		}
	}
	
	/**
	 * get graph density
	 */
	public static <V extends Vertex, E extends Edge> double getDensity(Graph<V, E> g)
	{
		double numerator = 2 * g.getEdgeCount();
		double denominator = g.getVertexCount() * (g.getVertexCount() - 1);
		
		return numerator / denominator;
	}
	
	/**
	 * get subgraph
	 */
	public static <V extends Vertex, E extends Edge> Graph<V, E> getSubGraph(Graph<V, E> g, Collection<String> ids)
	{
		try
		{
			Graph<V, E> graph = new SparseGraph<V, E>();
			
			Hashtable<String, V> idActors = new Hashtable<String, V>();
		
			Collection<V> actors1 = g.getVertices();
			
			for (V v : actors1)
			{
				if (ids.contains(v.getId()))
				{
					graph.addVertex(v);
					idActors.put(v.getId(), v);
				}
			}
			
			Collection<E> links = g.getEdges();
			
			if (g.getDefaultEdgeType() == EdgeType.UNDIRECTED)
			{
				for (E e : links)
				{
					Pair<V> pair = g.getEndpoints(e);
					V fromActor = idActors.get(pair.getFirst().getId());
					V toActor = idActors.get(pair.getSecond().getId());
					
					if (fromActor != null && toActor != null)
					{
						graph.addEdge(e, fromActor, toActor, EdgeType.UNDIRECTED);
					}
				}
			}
			else
			{
				for (E e : links)
				{
					V fromActor = idActors.get(g.getSource(e).getId());
					V toActor = idActors.get(g.getDest(e).getId());
					
					if (!(graph.isSource(fromActor, e) && graph.isDest(toActor, e)) && fromActor != toActor)
					{
						graph.addEdge(e, fromActor, toActor, EdgeType.DIRECTED);
					}
				}
			}
			
			return graph;
		}
		catch(Exception e)
		{
			log.error("Unable to get subgraph: " + e.getMessage());
			return null;
		}
	}
	
	/**
	 * get subgraph
	 */
	public static <V extends Vertex, E extends Edge> Graph<V, E> getSubGraph2(Graph<V, E> g, Collection<V> actors)
	{
		try
		{
			Graph<V, E> graph = new SparseGraph<V, E>();
			
			Hashtable<String, V> idActors = new Hashtable<String, V>();
		
			Collection<V> actors1 = g.getVertices();
			
			for (V v : actors1)
			{
				if (actors.contains(v))
				{
					graph.addVertex(v);
					idActors.put(v.getId(), v);
				}
			}
			
			Collection<E> links = g.getEdges();
			
			if (g.getDefaultEdgeType() == EdgeType.UNDIRECTED)
			{
				for (E e : links)
				{
					Pair<V> pair = g.getEndpoints(e);
					V fromActor = idActors.get(pair.getFirst().getId());
					V toActor = idActors.get(pair.getSecond().getId());
					
					if (fromActor != null && toActor != null)
					{
						graph.addEdge(e, fromActor, toActor, EdgeType.UNDIRECTED);
					}
				}
			}
			else
			{
				for (E e : links)
				{
					V fromActor = idActors.get(g.getSource(e).getId());
					V toActor = idActors.get(g.getDest(e).getId());
					
					if (!(graph.isSource(fromActor, e) && graph.isDest(toActor, e)) && fromActor != toActor)
					{
						graph.addEdge(e, fromActor, toActor, EdgeType.DIRECTED);
					}
				}
			}
			
			return graph;
		}
		catch(Exception e)
		{
			log.error("Unable to get subgraph: " + e.getMessage());
			return null;
		}
	}
	
	/**
	 * export graph to GraphML file
	 */
	public static <V extends Vertex, E extends Edge> void exportAsGraphMl(Graph<V, E> g, String fileName) 
	{
		try 
		{
			BufferedWriter out = new BufferedWriter(new FileWriter(fileName));

			GraphMLWriter<V, E> writer = new GraphMLWriter<V, E>();

			// add the vertex and edge transformers to set vertex and edge IDs
			Transformer<V, String> vertexIdTransformer = StringValueTransformer.getInstance();
			Transformer<E, String> edgeIdTransformer = StringValueTransformer.getInstance();
			
			writer.setVertexIDs(vertexIdTransformer);
			writer.setEdgeIDs(edgeIdTransformer);

			writer.save(g, out);

			out.close();
		} 
		catch (Exception e)
		{
			log.error("The graph could not be exported as a GraphML file: "+ e.getMessage());
		}
	}

	/**
	 * export graph to GraphML file
	 */
	public static <V extends Vertex, E extends Edge> void exportAsGraphMl(Graph<V, E> g)
	{
		exportAsGraphMl(g, GRAPHML_FILENAME);
	}
	
	/**
	 * load graph from a GraphML file
	 */
	public static Graph<Vertex, Edge> loadGraphMl(String filePath)
	{
		try 
		{
			BufferedReader in = new BufferedReader(new FileReader(filePath));

			Transformer<GraphMetadata, Graph<Vertex, Edge>> graphTransformer = new GraphTransformer<Vertex, Edge>();
			Transformer<NodeMetadata, Vertex> vertexTransformer = new VertexTransformer();
			Transformer<EdgeMetadata, Edge> edgeTransformer = new EdgeTransformer();
			Transformer<HyperEdgeMetadata, Edge> hyperEdgeTransformer = new HyperEdgeTransformer();

			GraphMLReader2<Graph<Vertex, Edge>, Vertex, Edge> reader = new GraphMLReader2<Graph<Vertex, Edge>, Vertex, 
					Edge>(in, graphTransformer, vertexTransformer, edgeTransformer, hyperEdgeTransformer);

			Graph<Vertex, Edge> g = reader.readGraph();

			reader.close();
			in.close();

			return g;
		} 
		catch (Exception e)
		{
			log.error("The GraphML file could not be loaded: " + e.getMessage());
			return null;
		}
	}
	
	/**
	 * get labeled nodes coordinates 
	 */
	public static Hashtable<String,Point2D.Float> getLabeledNodesCoordinates(String graphMlFilePath)
	{
		try
		{
			BufferedReader in = new BufferedReader(new FileReader(graphMlFilePath));
			Hashtable<String,Point2D.Float> coordinates = new Hashtable<String,Point2D.Float>();
			
			String label = null;
			float x = 0;
			float y = 0;
			
			String s;
			
			while((s = in.readLine()) != null)
			{
				if (s.contains("label "))
				{
					int qPos1 = s.indexOf('"');
					int qPos2 = s.indexOf('"', qPos1 + 1);
					
					label = s.substring(qPos1 + 1, qPos2);
				}
				else if (s.contains("x "))
				{
					int xPos = s.indexOf("x ");
					
					x = new Float(s.substring(xPos + 1).trim());
				}
				else if (s.contains("y "))
				{
					int yPos = s.indexOf("y ");
					
					y = new Float(s.substring(yPos + 1).trim());
					
					Point2D.Float point = new Point2D.Float(x, y);
					log.debug("Adding labeled coordinate: " + label + " " + x + ":" + y);
					coordinates.put(label, point);
				}
			}
			
			in.close();
			
			return coordinates;
		}
		catch(Exception e)
		{
			log.error("Unable to get labeled nodes coordinates: " + e.getMessage());
			return null;
		}
	}
	
	/**
	 * get actor by ID
	 */
	public static <V extends Vertex, E extends Edge> V getActorById(Graph<V, E> graph, String id)
	{
		try
		{
			Collection<V> actors = graph.getVertices();
			
			for (V v: actors)
			{
				if (v.getId().equals(id))
				{
					return v; 
				}
			}
			
			log.info("Actor '" + id + "' was not found in the graph");
			
			return null;
		}
		catch(Exception e)
		{
			log.error("Unable to get actor with id '" + id + "': " + e.getMessage());
			return null;
		}
	}
	
	/**
	 * merge 2  graphs having same edge type (directed or undirected) 
	 */
	public static <V extends Vertex, E extends Edge> Graph<V, E> mergeGraphs(Graph<V, E> g1, Graph<V, E> g2)
	{
		try
		{
			Graph<V, E> graph = new SparseGraph<V, E>();
			
			Hashtable<String, V> idActors = new Hashtable<String, V>();
		
			Collection<V> actors1 = g1.getVertices();
			Collection<V> actors2 = g2.getVertices();
			
			for (V v : actors1)
			{
				graph.addVertex(v);
				idActors.put(v.getId(), v);
			}
			
			for (V v : actors2)
			{
				V alreadyAdded = idActors.get(v.getId());
				
				// add a new vertex only if not already present
				if (alreadyAdded == null)
				{
					graph.addVertex(v);
					idActors.put(v.getId(), v);
				}
			}
			
			Collection<E> links1 = g1.getEdges();
			Collection<E> links2 = g2.getEdges();
			
			if (g1.getDefaultEdgeType() == EdgeType.UNDIRECTED)
			{
				for (E e : links1)
				{
					Pair<V> pair = g1.getEndpoints(e);
					V fromActor = idActors.get(pair.getFirst().getId());
					V toActor = idActors.get(pair.getSecond().getId());
					
					if (!graph.isNeighbor(fromActor, toActor) && fromActor != toActor)
					{
						graph.addEdge(e, fromActor, toActor, EdgeType.UNDIRECTED);
					}
				}
			}
			else
			{
				for (E e : links1)
				{
					V fromActor = idActors.get(g1.getSource(e).getId());
					V toActor = idActors.get(g1.getDest(e).getId());
					
					if (!(graph.isSource(fromActor, e) && graph.isDest(toActor, e)) && fromActor != toActor)
					{
						graph.addEdge(e, fromActor, toActor, EdgeType.DIRECTED);
					}
				}
			}
			
			if (g2.getDefaultEdgeType() == EdgeType.UNDIRECTED)
			{
				for (E e : links2)
				{
					Pair<V> pair = g2.getEndpoints(e);
					V fromActor = idActors.get(pair.getFirst().getId());
					V toActor = idActors.get(pair.getSecond().getId());
					
					if (!graph.isNeighbor(fromActor, toActor) && fromActor != toActor)
					{
						graph.addEdge(e, fromActor, toActor, EdgeType.UNDIRECTED);
					}
				}
			}
			else
			{
				for (E e : links2)
				{
					V fromActor = idActors.get(g1.getSource(e).getId());
					V toActor = idActors.get(g1.getDest(e).getId());
					
					if (!(graph.isSource(fromActor, e) && graph.isDest(toActor, e)) && fromActor != toActor)
					{
						graph.addEdge(e, fromActor, toActor, EdgeType.DIRECTED);
					}
				}
			}
			
			return graph;
		}
		catch(Exception e)
		{
			log.error("Unable to merge graphs: " + e.getMessage());
			return null;
		}
	}
	
	/**
	 * export graph to GML file
	 */
	public static <V extends Vertex, E extends Edge> void exportAsGml(Graph<V, E> g) 
	{
		exportAsGml(g, true, GML_FILENAME);
	}
	
	/**
	 * export graph to GML file
	 */
	public static <V extends Vertex, E extends Edge> void exportAsGml(Graph<V, E> g, String fileName) 
	{
		exportAsGml(g, true, fileName);
	}
	
	/**
	 * export graph to GML file
	 */
	public static <V extends Vertex, E extends Edge> void exportAsGml(Graph<V, E> g, boolean displayLabels, String fileName) 
	{
		try 
		{
			PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter(fileName)));

			out.println("graph [");
			out.println("	version 1");
			out.println("	Creator \"Sonedyan\"");

			if (g instanceof UndirectedSparseGraph<?, ?>)
			{
				out.println("	directed 0");
			} 
			else if (g instanceof DirectedSparseGraph<?, ?>)
			{
				out.println("	directed 1");
			}

			Collection<V> vertices = g.getVertices();
			
			int nodeCounter = 1;

			// hashtable actor ID -> node count
			Hashtable<String, Integer> actorIds = new Hashtable<String, Integer>();

			for (V v : vertices)
			{
				out.println("node");
				out.println("	[");
				out.println("	id " + nodeCounter);

				if (displayLabels)
				{
					out.println("	label \"" + v.getId() + "\"");
				}
				
				String nodeRadius = "0.9";
				String width = "0.0";
				String nodeFillColor = "#FF0000";
				String nodeOutlineColor = "#000000";
				String nodeLabelFillColor = "#000000";

				Random random = new Random();

				out.println("	labelAnchor \"nw\"");
				out.println("	graphics");
				out.println("	[");
				out.println("		x " + (random.nextFloat() * 100));
				out.println("		y " + (random.nextFloat() * 100));
				out.println("		w " + nodeRadius);
				out.println("		h " + nodeRadius);
				out.println("		type \"oval\"");
				out.println("		width " + width);
				out.println("		fill \"" + nodeFillColor + "\"");
				out.println("		outline \"" + nodeOutlineColor + "\"");
				out.println("	]");
				out.println("	LabelGraphics");
				out.println("	[");
				out.println("		type \"text\"");
				out.println("		font \"Courier\"");
				out.println("		fill \"" + nodeLabelFillColor + "\"");
				out.println("		anchor \"nw\"");
				out.println("	]");
				out.println("]");

				actorIds.put(v.getId(), nodeCounter);
				nodeCounter++;
			}

			Collection<E> edges = g.getEdges();

			String edgeWidth = "0.2";
			String edgeFillColor = "#0000FF";

			for (E e : edges) 
			{
				out.println("edge [");

				// remove labels for better visualization
				// out.println("	label \"" + link.toString() + "\"");

				out.println("	source " + actorIds.get(e.getFromActorId()));
				out.println("	target " + actorIds.get(e.getToActorId()));
				out.println("	graphics");
				out.println("	[");
				out.println("	type \"line\"");
				out.println("	arrow \"none\"");
				out.println("	fill \"" + edgeFillColor + "\"");
				out.println("	width " + edgeWidth);
				out.println("	]");
				out.println("	]");
			}

			out.println("]");

			out.close();
		} 
		catch (Exception e) 
		{
			log.error("The graph could not be exported as a GML file: " + e.getMessage());
		}
	}
	
	/**
	 * export graph to GML file and use the coordinates hashtable
	 */
	public static <V extends Vertex, E extends Edge> void exportAsGml(Graph<V, E> g, boolean displayLabels, Hashtable<String,Point2D.Float> coordinates, String fileName) 
	{
		try 
		{
			PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter(fileName)));

			out.println("graph [");
			out.println("	version 1");
			out.println("	Creator \"Sonedyan\"");

			if (g instanceof UndirectedSparseGraph<?, ?>)
			{
				out.println("	directed 0");
			} 
			else if (g instanceof DirectedSparseGraph<?, ?>)
			{
				out.println("	directed 1");
			}

			Collection<V> vertices = g.getVertices();
			
			int nodeCounter = 1;

			// hashtable actor ID -> node count
			Hashtable<String, Integer> actorIds = new Hashtable<String, Integer>();

			for (V v : vertices)
			{
				out.println("node");
				out.println("	[");
				out.println("	id " + nodeCounter);

				if (displayLabels)
				{
					out.println("	label \"" + v.getId() + "\"");
				}
				
				String nodeRadius = "0.9";
				String width = "0.0";
				String nodeFillColor = "#FF0000";
				String nodeOutlineColor = "#000000";
				String nodeLabelFillColor = "#000000";
				
				Point2D.Float point = coordinates.get(v.getId());
				Random random = new Random();
				
				float x = 0;
				float y = 0;
				
				if (point != null)
				{
					x = point.x;
					y = point.y;
				}
				else
				{
					x = random.nextFloat() * 100;
					y = random.nextFloat() * 100;
				}
				
				out.println("	labelAnchor \"nw\"");
				out.println("	graphics");
				out.println("	[");
				out.println("		x " + x);
				out.println("		y " + y);
				out.println("		w " + nodeRadius);
				out.println("		h " + nodeRadius);
				out.println("		type \"oval\"");
				out.println("		width " + width);
				out.println("		fill \"" + nodeFillColor + "\"");
				out.println("		outline \"" + nodeOutlineColor + "\"");
				out.println("	]");
				out.println("	LabelGraphics");
				out.println("	[");
				out.println("		type \"text\"");
				out.println("		font \"Courier\"");
				out.println("		fill \"" + nodeLabelFillColor + "\"");
				out.println("		anchor \"nw\"");
				out.println("	]");
				out.println("]");

				actorIds.put(v.getId(), nodeCounter);
				nodeCounter++;
			}

			Collection<E> edges = g.getEdges();
			
			String edgeWidth = "0.2";
			String edgeFillColor = "#0000FF";

			for (E e : edges) 
			{
				out.println("edge [");

				// remove labels for better visualization
				// out.println("	label \"" + link.toString() + "\"");

				out.println("	source " + actorIds.get(e.getFromActorId()));
				out.println("	target " + actorIds.get(e.getToActorId()));
				out.println("	graphics");
				out.println("	[");
				out.println("	type \"line\"");
				out.println("	arrow \"none\"");
				out.println("	fill \"" + edgeFillColor + "\"");
				out.println("	width " + edgeWidth);
				out.println("	]");
				out.println("	]");
			}

			out.println("]");

			out.close();
		} 
		catch (Exception e) 
		{
			log.error("The graph could not be exported as a GML file: " + e.getMessage());
		}
	}
	
	/**
	 * extract an undirected sparse graph from the initial undirected multi graph
	 */
	public static <V extends Vertex, E extends Edge> UndirectedGraph<V, E> extractUndirectedGraphFromMultiGraph(SparseMultigraph<V, E> multiGraph)
	{
		UndirectedSparseGraph<V, E> graph = new UndirectedSparseGraph<V, E>();
		
		try
		{
			Collection<V> vertices = multiGraph.getVertices();
			Hashtable<String, V> actorHash = new Hashtable<String, V>();
			
			for (V v : vertices)
			{
				graph.addVertex(v);
				actorHash.put(v.getId(), v);
			}
			
			Collection<E> edges = multiGraph.getEdges();
			
			// if multiple edges exist between two actors, only one is added
			for (E e : edges)
			{
				V v1 = actorHash.get(e.getFromActorId());
				V v2 = actorHash.get(e.getToActorId());
				
				if (!graph.isNeighbor(v1, v2) && v1 != v2)
				{
					graph.addEdge(e, v1, v2, EdgeType.UNDIRECTED);
				}	
			}
			
			return graph;
		}
		catch(Exception e)
		{
			log.error("Unable to extract graph from multigraph: " + e.getMessage());
			return null;
		}
	}

	/**
	 * export graph to Pajek file
	 */
	public static <V extends Vertex, E extends Edge> void exportAsPajek(Graph<V, E> g, String fileName)
	{
		try
		{
			PajekNetWriter<V, E> writer = new PajekNetWriter<V, E>();
			writer.save(g, fileName);
		} 
		catch (Exception e)
		{
			log.error("The graph could not be exported as a Pajek file: " + e.getMessage());
		}
	}

	/**
	 * export graph to Pajek file
	 */
	public static <V extends Vertex, E extends Edge> void exportAsPajek(Graph<V, E> g) 
	{
		exportAsPajek(g, PAJEK_FILENAME);
	}
}
